A system called grid computing has attracted people's attention in recent years that integrates and uses heterogeneous information systems interconnected through a network. In this system, computer resources such as CPU power and data storage of multiple computers on the network are shared so that the system is used as a single, virtual high-performance computer. By causing the multiple computers to perform parallel processing, a large amount of processing can be performed at high speeds even though the performances of the individual computers are low.
In grid computing, scheduling which determines the execution sequence of jobs (units of processing in a program) provided to the system according to the characteristics and priorities of the jobs is extremely important. This is because, in a grid environment which is inherently heterogeneous, jobs must be assigned to multiple computers having different performances and execution of various jobs of different sizes provided from remote users as well as local users must be properly scheduled.
Scheduling schemes in grid computing can be broadly classified into two types: push and pull. In the push type scheduling (see Non-patent document 1 for example), when a job is submitted to a scheduler, the scheduler assigns a computer to execute the job and requests the computer to execute the job. For doing this, the scheduler monitors the status of the computers and assigns the job to the most suitable computer according to load information of the job.
The push type scheduling scheme is often used in a grid system called a cluster grid that consists of several hundred servers (computers) provided at the same site. The push type scheduling scheme can assign a job specifically to the most suitable computer and therefore can provide optimum scheduling. Especially, in an environment where there are variations in behavior of computers and a job can be canceled on a computer when a user uses the computer, this scheme can provide optimum scheduling by taking such an operating environment into consideration to enable very efficient utilization of the system.
In the pull type scheduling (see Non-patent document 2 for example) on the other hand, each computer polls a scheduler to request a job when the computer becomes ready to execute a job. If there is a job to execute when the request is made, the scheduler assigns the job to the computer and the computer executes the assigned job. If there is no job to execute, the computer polls again after a lapse of predetermined time.
The pull type scheduling scheme can be implemented with a very simple configuration and, therefore, it is often used in grid systems consisting of several thousand computers. Especially, a grid built on the Internet uses this pull scheduling scheme because of constraints of the network. Furthermore, the pull type scheduling scheme can be readily applied to a large number of computers because management information about the computers is simple. Self-optimization by polling (that is, computers with higher availability perform polling more frequently) can improve the efficiency to some extent.
Non-patent document 1: Chris Smith, “Open Source Metascheduling for Virtual Organizations with the Community Scheduler Framework (CSF)”, Technical Whitepaper, Platform Computing Inc., August 2003
Non-patent document 2: Eric Korpela, Dan Werthimer, David Anderson, Jeff Cobb, Matt Lebofsky, “Massively Distributed Computing for SETI”, Computing in Science & Engineering, Vol. 3, Issue 1, January-February 2001, Pages 78-83